package Other.DP;

import java.net.Socket;

/**
 * @author:gao
 * @date:2020/7/10
 * @time:14:16
 * @version:0.0.1
 * @description:none
 */

//213. 打家劫舍 II
public class Rob2 {
    public static void main(String[] args) {

    }
}

class Solution1000 {
    public int rob(int[] nums) {
        if(nums.length==0) return 0;
        if(nums.length==1) return nums[0];
        if(nums.length==2) return Math.max(nums[0],nums[1]);
        int[] dp = new int[3];
        int len = nums.length-1;
        dp[0] = nums[0];
        dp[1] = Math.max(nums[1],nums[0]);
        boolean hasOne =false;
        if(dp[0]+nums[2]>dp[1]) {
            dp[2]= dp[0]+nums[2];
            hasOne = true;
        }else{
            dp[2]=dp[1];
            hasOne =false;
        }
        for(int i=3;i<nums.length-1;i++){
            dp[i%3] = Math.max(dp[(i-1)%3],dp[(i-2)%3]+nums[i]);
        }
        if(hasOne){
            dp[len%3] = dp[(len-1)%3];
        }else{

            dp[len%3] = Math.max(dp[(len-1)%3],dp[(len-2)%3]+nums[len]);
        }
        int max0 = dp[len%3];
        if(len>=3) {
            //从1开始计算
            dp[0] = nums[1];
            dp[1] = Math.max(nums[1], nums[2]);
            if (dp[0] + nums[3] > dp[1]) {
                dp[2] = dp[0] + nums[3];
            } else {
                dp[2] = dp[1];
            }
            for (int i = 4; i < nums.length; i++) {
                dp[(i-1)%3] = Math.max(dp[(i - 2)%3], dp[(i - 3)%3] + nums[i]);
            }
        }
        return Math.max(max0,dp[(len-1)%3]);

    }
}